淺談 C# 的 GetHashCode()

TLDR

覆寫 Equals() 時必須同時覆寫 GetHashCode()，否則 Dictionary 或 HashSet 等依賴雜湊的集合將無法正確識別相等物件。
GetHashCode() 的核心原則：相等物件必須回傳相同雜湊值；不相等物件則不強制要求不同值；方法本身不應拋出例外。
在 .NET Core 2.1+ 環境，建議使用 HashCode.Combine() 來實作 GetHashCode()。
Dictionary 搜尋時會先比對 HashCode，再比對 Equals()，此機制能有效提升效能並減少不必要的物件比對。

GetHashCode() 的實作原則與重要性

什麼情況下會遇到這個問題：當自訂類別作為 Dictionary 的 Key 或存入 HashSet 時，若僅覆寫 Equals() 而未同步處理 GetHashCode()，會導致集合無法正確判斷物件是否重複。

GetHashCode() 用於產生整數型雜湊值，是 Dictionary<TKey, TValue>、HashSet<T> 以及 LINQ Distinct() 等方法的運作基礎。實作時必須遵守以下原則：

若兩個物件經 Equals() 判斷為相等，則 GetHashCode() 必須回傳相同數值。
若兩個物件不相等，則 GetHashCode() 不強制要求回傳不同值（允許雜湊碰撞）。
GetHashCode() 不應拋出例外狀況。

若未遵守上述原則，即使邏輯上相等的物件，在集合中也會被視為不同個體。以下為錯誤範例：

csharp

public class Test {
    public string Name { get; set; }
    public int Age { get; set; }

    public override bool Equals(object obj) => obj is Test test && Name == test.Name && Age == test.Age;
}

// 測試結果
Test test1 = new() { Name = "王大明", Age = 10 };
Test test2 = new() { Name = "王大明", Age = 10 };
Dictionary<Test, string> dic = new() { [test1] = "測試" };

Console.WriteLine(test1.Equals(test2)); // True
Console.WriteLine(dic.ContainsKey(test2)); // False

實作建議

什麼情況下會遇到這個問題：在開發過程中，若需要手動實作 GetHashCode() 以確保物件比對正確性時。

針對不同 .NET 版本，建議採取以下做法：

.NET Core 2.1 以上版本：使用 HashCode.Combine()，這是最簡潔且效能良好的方式。
csharp
```
public override int GetHashCode() => HashCode.Combine(Name, Age);
```
1

.NET Framework 版本：由於不支援 HashCode.Combine()，建議手動組合欄位雜湊值，並使用質數作為乘數以減少碰撞。

csharp

public override int GetHashCode() {
    int hashCode = -1360180430;
    hashCode = hashCode * -1521134295 + EqualityComparer<string>.Default.GetHashCode(Name);
    hashCode = hashCode * -1521134295 + Age.GetHashCode();
    return hashCode;
}

TIP

使用 EqualityComparer<T>.Default 計算雜湊值，可以妥善處理 null 值並確保不同類別間的運算規則一致。

Dictionary 的搜尋機制與效能優化

什麼情況下會遇到這個問題：當需要理解為什麼 Dictionary 在處理大量資料時，比對速度依然能維持高效能。

Dictionary 內部透過 _buckets 與 _entries 兩個陣列結構來儲存資料。其搜尋方法 FindValue() 的運作流程如下：

計算雜湊值：先計算 Key 的 HashCode，用以定位 _buckets 中的索引，直接存取對應的 _entries，避免全域搜尋。
初步篩選：先比對 HashCode 是否一致。若 HashCode 不同，則直接判定不相等，無需呼叫成本較高的 Equals() 方法。
處理碰撞：若 HashCode 相同但物件內容不同（雜湊碰撞），則透過 entry.next 指標逐一比對鏈結中的物件，直到找到匹配值。

此機制確保了在大多數情況下，集合操作能以接近 O(1) 的時間複雜度完成。

異動歷程

2024-09-01 初版文件建立。

筆記目錄

淺談 C# 的 GetHashCode() ​

TLDR ​

GetHashCode() 的實作原則與重要性 ​

實作建議 ​

Dictionary 的搜尋機制與效能優化 ​

異動歷程 ​